In some cases, a block matching process performed with the use of a criteria image and a reference image on a block-by-block basis causes a difference in tone between blocks adjacent to each other. Such a difference in tone often occurs particularly in regions where tone changes slowly. Noise caused by such a difference in tone is called block noise.
Meanwhile, an apparatus that encodes images by MPEG-4 (Moving Picture Experts Group phase 4) or H.264/AVC (Advanced Video Coding) includes a deblocking filter that performs a deblocking process to remove block noise (see Non-Patent Document 1). Degradation of image quality can be reduced by smoothing the boundary portions of blocks through the deblocking process.